1. Field Of The Invention
This invention relates to Rivest, Shamir and Adleman (RSA) public cryptosystems and more particularly to a computer and computer programming for identity verification, forming joint signatures, and session key agreement in an RSA type system.
2. Description of the Related Art
Encryption systems have been developed for maintaining the privacy of information transmitted across a communications channel. Typically, a symmetric cryptosystem is used for this purpose. Symmetric cryptosystems, which utilize electronic keys, can be likened to a physical security system where a box has a single locking mechanism with a single key hole. One key holder uses his/her key to open the box, place a message in the box and relock the box. Only a second holder of the identical copy of the key can unlock the box and retrieve the message. The term symmetric reflects the fact that both users must have identical copies of the key.
In more technical terms, a symmetric cryptosystem uses an encryption function E, a decryption function D, and a shared secret-key, K. The secret-key is a unique string of data bits to which the functions are applied. Two examples of encipherment/deencipherment functions are the National Bureau of Standards Data Encryption Standard (DES) and the more recent Fast Encipherment Algorithm (FEAL). To transmit a message, M, in privacy, the sender computes M=E (C,K), where C is referred to as the ciphertext. Upon receipt of C, the recipient computes M=D (C,K), to recover the message M. An eavesdropper who copies C, but does not know K, will find it practically impossible to recover M. Typically, all details of the enciphering and deciphering functions, E and D, are well known, and the security of the system depends solely on maintaining the secrecy of key, K. Conventional symmetric cryptosystems are fairly efficient and can be used for encryption at fairly high data rates, especially if appropriate hardware implementations are used.
Asymmetric cryptosystems, often referred to as public key cryptosystems, provide another means of encrypting information. Such systems differ from symmetric systems in that, in terms of physical analogue, the box has one lock which accepts different keys. One key can be used to unlock the box to retrieve a message which has been locked in the box by the other key.
In public key electronic cryptosystems, each entity, for example, x and y, has a private key, d, which is known only to the entity, and a public key, e, which is publicly known. Once a message is transformed with a user's public-key, it can only be inverted using that user's private-key, and conversely, if a message is transformed with a user's private-key, it can only be inverted using that user's public-key. So, if sender x wishes to send a message to receiver y, then x, "looks-up" y's public key e, and computes M=E (C, e.sub.y) and sends it to y. User y can recover M using its private-key d.sub.y, by computing M=D(C, d.sub.y). An adversary who makes a copy of C, but does not have d.sub.y, cannot recover M. However, public-key cryptosystems are inefficient for large messages.
Public-key cryptosystems are quite useful for digital signatures. The signer, x, computes S=D(M, d.sub.x) and sends M,S! to y. User y "looks-up" x's public-key e.sub.x, and then checks to see if M=D (S, e.sub.x). If it does, then y can be confident that x signed the message, since computing S, such that M=D (S, e.sub.x), requires knowledge of d.sub.x, x's private key which only x knows.
Public-key cryptography also provide a convenient way of performing session key agreement, after which the key that was agreed upon can be used for symmetric encryption. Typically, the key being exchanged is used during the course of a particular communication session and then destroyed, though this can vary depending on the application.
One public key cryptographic system is the Rivest, Shamir, Adleman (RSA) system, as described in Rivest, Shamir and Adleman, "A Method of Obtaining Digital Signatures and Public Key Cryptosystems, CACM, Vol 21, pp 120-126, February 1978. RSA is a public-key based cryptosystem that is believed to be very difficult to break. In the RSA system the pair (e.sub.i N.sub.i), is user i's public-key and d.sub.i is the user's private key. Here N.sub.i =pq, where p and q are large properly chosen primes. Here also ed=1 mod .phi.(N.sub.i) , where .phi.(N.sub.i)=(p-1) (q-1) which is the Euler Totient function which returns the number of positive integers less than N.sub.i, that are relatively prime to N.sub.i. A Carmichael function is sometimes used in lieu of a Euler Totient function.
To send a message to user j, user i can compute C=M.sup.(e.sbsp.j.sup.) modN.sub.j and send C to user j. User j will then perform M=C.sup.(d.sbsp.j.sup.) modN.sub.j to recover M. Alternatively, user i could sign the message using his private key. The RSA based signature of user i on the message, M, is M.sup.d.sbsp.i modN.sub.i. The recipient of the message, user j, can perform .sup.(M (d.sbsp.i.sup.) modN.sub.i) .sup.(e.sbsp.i.sup.) modN.sub.i, to verify the signature of i on M.
In a typical mode of operation, i sends j, M.sup.(d.sbsp.i.sup.) modN.sub.i along with M and a certificate C=(i,e.sub.i N.sub.i).sup.d.sbsp.CA modN.sub.CA, where C is generated by a Certification Authority (CA) which serves as a trusted off-line intermediary. User j can recover i's public key from C, by performing C.sup.(e.sbsp.CA.sup.) modN.sub.CA, as e.sub.CA and N.sub.CA are universally known. It should also be noted that in an RSA system the encryption and signatures can be combined.
Modifications to RSA systems have been proposed to enable multi-signatures to be implemented in a manner which only requires a single RSA transformation. The proposed approach extends the RSA system by dividing the user private key d into two portions, say d.sub.i and d.sub.j, where d.sub.i *d.sub.j =dmod .phi.(N). Such a proposal is described in Digital Multisignature, C. Boyd, Proceedings of the Inst. of Math, and its Appl. on Cryptography and Coding, 15-17 December 1986.
However the problem remains that conventional RSA systems, including those modified as proposed, require that the secret exponent key d of a user be quite long. In the case where the secret exponent d is less than a quarter of the length of the modulus N, RSA is insecure, because it is too easy to invert the public operation without the secret key. Such a conclusion is discussed in M. J. Wiener "Cryptoanalysis of short RSA Secret Exponents, IEEE Trans. on IT, May 1990, Vol. 36, No. 3, pp. 553-558. Thus, according to Wiener, if the modulus N is 512 bits long, the secret exponent should have at least 128 bits. Accordingly, conventional RSA systems are not suitable for use in systems that do not provide a way to store the secret exponent key d. e.g. in situations where the user has to memorize the secret exponent. This, for example, is the case when smart cards for storing the secret exponent are not widely available or when the user accesses the distributed system via a dumb terminal that does not have a disk drive for storing the secret exponent. Additionally, conventional RSA systems do not provide a way to establish and distribute session keys using split private keys.
Therefore, it is an object of the present invention to provide a programmable computer and computer programming instructions for improving conventional RSA public cryptosystems so that the user is only required to use a short secret key while the system provides security as high as that of conventional RSA systems.
It is another object of the invention to provide a programmable computer and computer programming instructions for improving conventional RSA cryptosystems it such that the identity of the user can be verified when the user is using a short secret key.
It is a further object of the invention to provide a programmable computer and computer programming instructions for improving conventional RSA cryptosystems such that joint signature of documents by two or more users is facilitated using a short secret key of a user.
It is a still further object of the present invention to provide a programmable computer and computer programming instructions to improve conventional RSA cryptosystems so that session key agreement can be accomplished using split private keys.
Additional objects, advantages and novel features of the present invention will become apparent to those skilled in the art from the following detailed, as well as by practice of the invention. While the invention is described below with reference to preferred embodiments, it should be understood that the invention is not limited thereto. Those of ordinary skill in the art having access to the teachings herein will recognize additional implementations, modifications and embodiments which are within the scope of the invention as disclosed and claimed herein and with respect to which the invention could be of significant utility.